/**
 * 
 */
package fhq.hcmute.qrcode.reedsolomon;

import java.util.ArrayList;

import fhq.hcmute.qrcode.util.QRCodeException;

/**
 * @author Hien Nguyen Le
 * @Email: nglehien@gmail.com
 */
public class Polynomial {

	private ArrayList<Monomial> monomials;

	private Polynomial quotient;
	private Polynomial remainder;

	public Polynomial() {
		monomials = new ArrayList<Monomial>();
	}

	public Polynomial(ArrayList<Monomial> monomials) {
		this.monomials = new ArrayList<Monomial>(monomials);
	}

	public static Polynomial createPolynomial(int[] integerValues, int exponent)
			throws QRCodeException {
		Polynomial messagePolynomial = new Polynomial();
		for (int i = 0; i < integerValues.length; i++) {
			Monomial monomial = new Monomial(integerValues[i], exponent - i);
			messagePolynomial.add(monomial);
		}
		return messagePolynomial;
	}

	public Polynomial(Monomial... arrMono) {
		this.monomials = new ArrayList<Monomial>();
		for (Monomial i : arrMono) {
			this.monomials.add(i);
		}
	}

	public int getMaxExponent() {
		return monomials.get(0).getExponent();
	}

	public int getMinExponent() {
		return monomials.get(monomials.size() - 1).getExponent();
	}

	/**
	 * Add a monoial to Polynomial, XOR if exponent exists
	 * 
	 * @param monomial
	 * @throws QRCodeException
	 */
	public void add(Monomial monomial) throws QRCodeException {
		boolean isContains = false;
		for (int i = 0; i < monomials.size(); i++) {
			if (monomials.get(i).getExponent() == monomial.getExponent()) {
				monomials.set(i, monomials.get(i).xor(monomial));
				isContains = true;
			}
		}
		if (!isContains) {
			monomials.add(monomial);
		}
		sort();
	}

	public void add(Polynomial polynomial) throws QRCodeException {
		for (Monomial i : polynomial.monomials) {
			add(i);
		}
		ArrayList<Monomial> result = new ArrayList<Monomial>();
		for (Monomial m : this.monomials) {
			if (m.getCoefficient() != 0) {
				result.add(m);
			}
		}
		this.monomials = result;
	}

	public Monomial get(int i) {
		return this.monomials.get(i);
	}

	public void set(int i, Monomial monomial) {
		this.monomials.set(i, monomial);
	}

	public Polynomial multiply(Monomial monomial) throws QRCodeException {
		Polynomial temp = new Polynomial(monomials);
		for (int i = 0; i < temp.getSize(); i++) {
			Monomial mono = temp.get(i);
			mono = mono.multiply(monomial);
			temp.set(i, mono);
		}
		sort();

		return temp;
	}

	public Polynomial multiply(int coeff, int exponent) throws QRCodeException {
		Polynomial temp = new Polynomial(monomials);
		Monomial monomial = new Monomial();
		monomial.setCoefficient(coeff);
		monomial.setExponent(exponent);
		for (int i = 0; i < temp.getSize(); i++) {
			Monomial mono = temp.get(i);
			mono = mono.multiply(monomial);
			temp.set(i, mono);
		}
		sort();
		return temp;
	}

	public void multiply(Polynomial polynomial) throws QRCodeException {
		ArrayList<Polynomial> polynomials = new ArrayList<Polynomial>();
		for (Monomial mono : polynomial.monomials) {
			Polynomial temp = new Polynomial(monomials);
			temp = temp.multiply(mono);
			polynomials.add(temp);
		}
		Polynomial result = new Polynomial();
		for (Polynomial temp : polynomials) {
			result.add(temp);
		}
		this.monomials = result.monomials;
	}

	public void reduceExponent() {
		int max = this.getMaxExponent() - 1;
		for (Monomial i : this.monomials) {
			i.setExponent(max);
			max--;
		}
	}

	public void reduceExponent(int n) {
		int max = this.getMaxExponent() - n;
		for (Monomial i : this.monomials) {
			i.setExponent(max);
			max--;
		}
	}

	private void sort() {
		for (int i = 0; i < monomials.size(); i++) {
			for (int j = 0; j < monomials.size(); j++) {
				if (monomials.get(i).getExponent() > monomials.get(j)
						.getExponent()) {
					Monomial temp = monomials.get(i);
					monomials.set(i, monomials.get(j));
					monomials.set(j, temp);
				}
			}
		}
	}

	@Override
	public String toString() {
		String temp = "";
		for (Monomial monomial : monomials) {
			temp += monomial.toString() + "     ";
		}
		return temp;
	}

	public int getSize() {
		return this.monomials.size();
	}

	public int getFirstCoefficient() {
		int max = getMaxExponent();
		for (Monomial m : this.monomials) {
			if (m.getExponent() == max) {
				return m.getCoefficient();
			}
		}
		return Integer.MIN_VALUE;
	}

	private boolean containsExponent(int exponent) {
		for (Monomial i : this.monomials) {
			if (i.getExponent() == exponent) {
				return true;
			}
		}
		return false;
	}

	public void xor(Polynomial polynomial) throws QRCodeException {
		ArrayList<Monomial> result = new ArrayList<Monomial>();
		int max = this.getMaxExponent() > polynomial.getMaxExponent() ? getMaxExponent()
				: polynomial.getMaxExponent();
		int min = this.getMinExponent() < polynomial.getMinExponent() ? getMinExponent()
				: polynomial.getMinExponent();
		for (int i = min; i <= max; i++) {
			if (!containsExponent(i)) {
				this.add(new Monomial(0, i));
			}
			if (!polynomial.containsExponent(i)) {
				polynomial.add(new Monomial(0, i));
			}
		}
		Monomial x = null;
		Monomial y = null;
		for (int i = 0; i < this.getSize(); i++) {
			x = this.monomials.get(i);
			y = polynomial.monomials.get(i);
			x = x.xor(y);
			if (x.getCoeffExponent() >= 0 || result.size() != 0) {
				result.add(x);
			}
		}
		this.monomials = result;
	}

	/**
	 * @Step 1: Multiply generator polynomial by first coefficient with the
	 *       Message Polynomial above.
	 * 
	 * @Step 2: XOR each term of the two above polynomials.
	 * 
	 * @Result: When the final term of the polynomial has X^0, we are done (for
	 *          1 block).
	 */

	public void devide(Polynomial generatorPolynomial) throws QRCodeException {
		remainder = new Polynomial(this.monomials);
		quotient = new Polynomial();
		int inverseCoefficient = GaloisFiled256.inverse(generatorPolynomial
				.getFirstCoefficient());
		while (remainder.getSize() != 0
				&& remainder.getMaxExponent() >= generatorPolynomial
						.getMaxExponent()) {
			int exponentDifference = remainder.getMaxExponent()
					- generatorPolynomial.getMaxExponent();
			int scale = GaloisFiled256.multiply(
					remainder.getFirstCoefficient(), inverseCoefficient);

			quotient.add(new Monomial(scale, exponentDifference));

			remainder.xor(generatorPolynomial.multiply(scale,
					exponentDifference));
		}
	}

	public int[] getArrayCoefficient() {
		int[] array = new int[this.getSize()];
		for (int i = 0; i < this.getSize(); i++) {
			array[i] = monomials.get(i).getCoefficient();
		}
		return array;
	}

	public int getCoefficientByExponent(int index) {
		for (Monomial i : this.monomials) {
			if (i.getExponent() == index) {
				return i.getCoefficient();
			}
		}
		return 0;
	}

	public int[] getArrayCoefficient(int n) {
		int[] array = new int[n];
		for (int i = n - 1; i >= 0; i--) {
			array[i] = getCoefficientByExponent(n - 1 - i);
		}
		return array;
	}

	public Polynomial getQuotient() {
		return quotient;
	}

	public Polynomial getRemainder() {
		return remainder;
	}

	public int evaluateAt(int x) throws QRCodeException {
		if (x == 1) {
			int result = 0;
			for (int i = 0; i < this.getArrayCoefficient().length; i++) {
				result ^= this.getArrayCoefficient()[i];
			}
			return result;
		}
		int y = this.getArrayCoefficient()[0];
		for (int i = 1; i < this.getArrayCoefficient().length; i++) {
			y = GaloisFiled256.multiply(y, x) ^ this.getArrayCoefficient()[i];
		}
		return y;
	}

}
